#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    // 这道题有点意思，需要逆向思考
    // 刚开始我使用前缀和加递归的方法求解，同时使用数组的平均值进行剪枝，无奈超时
    // 后来看题解发现还可以这么做，在有限的范围内二分查找承重的下限
    int shipWithinDays(vector<int>& weights, int days) {
        int r = 0;
        int l = 0;

        // 右边界为数组的和，左边界为数组中最大的值
        for (auto w : weights) {
            r += w;
            l = max(l, w);
        }

        while (l < r) {
            // 上次有道题目越界，现在都不敢直接 (l + r) >> 1
            int mid = l + ((r - l) >> 1);

            // 这里求承重为 mid 的前提下，需要 need 天
            int need = 1, current = 0;
            for (int i = 0; i < weights.size(); i++) {
                current += weights[i];
                if (current > mid) {
                    current = current == weights[i] ? 0 : weights[i];
                    need++;
                }
            }

            // 需要天数过多，则提高承重，否则降低承重
            if (need > days) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }

        return l;
    }
};

int main() {
    int days = 19;
    vector<int> weights = {120,112,305,241,68,321,461,87,397,180,180,95,96,268,191,416,396,228,277,234,168,435,18,238,217,296,316,374,465,7,149,166,107,87,18,4,480,223};

    cout << Solution().shipWithinDays(weights, days) << endl;

    return 0;
};